package com.xk._01基础篇._07AVL;

import com.xk._01基础篇._06二叉搜索树02.printer.BinaryTrees;
import com.xk._01基础篇._07AVL.tree.AVLTree;
import com.xk._01基础篇._07AVL.tree.BST;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: xu
 * @date: 2022/9/23 21:09
 */
public class Main {
    public static void main(String[] args) {
        test2();
    }

    static void test2() {
        List<Integer> data = new ArrayList<>();
        for (int i = 0; i < 100_0000; i++) {
            data.add((int)(Math.random() * 100_0000));
        }

        long l1 = System.currentTimeMillis();
        BST<Integer> bst = new BST<>();
        for (int i = 0; i < data.size(); i++) {
            bst.add(data.get(i));
        }
        for (int i = 0; i < data.size(); i++) {
            bst.contains(data.get(i));
        }
        for (int i = 0; i < data.size(); i++) {
            bst.remove(data.get(i));
        }
        long l2 = System.currentTimeMillis();

        AVLTree<Integer> avl = new AVLTree<>();
        for (int i = 0; i < data.size(); i++) {
            avl.add(data.get(i));
        }
        for (int i = 0; i < data.size(); i++) {
            avl.contains(data.get(i));
        }
        for (int i = 0; i < data.size(); i++) {
            avl.remove(data.get(i));
        }
        long l3 = System.currentTimeMillis();

        System.out.println("BST: " + (l2 - l1));
        System.out.println("AVL: " + (l3 - l2));
    }

    static void test01(){
        Integer[] nums = new Integer[]{
                67,52,92,96,53,95,13,63,34,82,76,54,9,68,39
        };

        AVLTree<Integer> avlTree = new AVLTree<>();
        for (int i = 0; i < nums.length; i++) {
            avlTree.add(nums[i]);
            System.out.println("insert【" + nums[i] + "】");
            BinaryTrees.println(avlTree);
            System.out.println("=============================================");
        }

        for (int i = 0; i < nums.length; i++) {
            avlTree.remove(nums[i]);
            System.out.println("remove【" + nums[i] + "】");
            BinaryTrees.println(avlTree);
            System.out.println("=============================================");
        }
    }
}
